﻿/**
 * @file std_hash.inl
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 定义 散列容器 内部相关数据类型、常量、宏 等。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef __STD_HASH_INL__
#define __STD_HASH_INL__

#ifndef __STD_HASH_H__
#error "Please include std_hash.h before this file."
#endif // __STD_HASH_H__

#include "std_list.h"
#include "std_list.inl"

////////////////////////////////////////////////////////////////////////////////
// xstd_hash_t 的相关数据类型定义

/** 散列表容器 类型 */
typedef xstd_list_t  xhash_table_t;

/** 散列表容器的 迭代器 类型 */
typedef xlst_iter_t  xhash_lter_t;

/**
 * @struct xhash_vkey_t
 * @brief  同一散列值的 节点对 结构体类型。
 */
typedef struct xhash_vkey_t
{
    xhash_lter_t  xlter_head;  ///< 同一散列值的 节点对 的 首端节点
    xhash_lter_t  xlter_tail;  ///< 同一散列值的 节点对 的 尾端节点
} xhash_vkey_t, * xhash_vter_t;

/**
 * @struct xstd_hash_t
 * @brief  散列容器的结构体描述信息。
 */
typedef struct xstd_hash_t
{
    xhash_table_t  xhash_table;  ///< 存储各个节点元素的散列表容器

    /**
     * 存储 xhash_bucket_t对象 的向量容器：
     * 每个桶节点由两个迭代器构成，表示桶中元素的封闭范围。
     */
    struct
    {
    xhash_vter_t   xhash_vptr;   ///< 散列桶的存储缓存
    xhash_size_t   xhash_vlen;   ///< 散列桶的存储容量（必须为 2^N 的整数值）
    xhash_size_t   xhash_mask;   ///< 散列桶的索引掩码
    xhash_float_t  xhash_maxf;   ///< 散列桶的最大负载率（默认为 1.0F）
    } xhash_bucket;

    xhash_nkfunc_t xhash_nkfunc; ///< 计算节点元素 散列值（索引键）的回调函数
    xhash_eqfunc_t xhash_eqfunc; ///< 判断节点元素 是否相等 的回调函数
} xstd_hash_t;

////////////////////////////////////////////////////////////////////////////////
// xstd_hash_t 的相关操作宏函数

//====================================================================

#define XHASH_TABLE(xhash_this)    (&((xhash_this)->xhash_table))

#define XHASH_ECTXT(xhash_this)    XLST_ECTXT(XHASH_TABLE(xhash_this))
#define XHASH_ETYPE(xhash_this)    XLST_ETYPE(XHASH_TABLE(xhash_this))
#define XHASH_ESIZE(xhash_this)    XLST_ESIZE(XHASH_TABLE(xhash_this))
#define XHASH_ALTOR(xhash_this)    XLST_ALTOR(XHASH_TABLE(xhash_this))

#define XHASH_MALLOC(xhash_this, xst_size)            \
            XLST_MALLOC(XHASH_TABLE(xhash_this), (xst_size))

#define XHASH_DEALLOC(xhash_this, xmt_mptr)           \
            XLST_DEALLOC(XHASH_TABLE(xhash_this), (xmt_mptr))

#define XHASH_ALFROM(xhash_this, xet_dptr, xet_sptr)  \
            XLST_ALFROM(XHASH_TABLE(xhash_this), (xet_dptr), (xet_sptr))

#define XHASH_ALMOVE(xhash_this, xet_dptr, xet_sptr)  \
            XLST_ALMOVE(XHASH_TABLE(xhash_this), (xet_dptr), (xet_sptr))

#define XHASH_ALDEST(xhash_this, xet_elem)            \
            XLST_ALDEST(XHASH_TABLE(xhash_this), (xet_elem))

#define XHASH_ISSAME_TYPE(xhash_lthis, xhash_rthis)    \
            XLST_ISSAME_TYPE(XHASH_TABLE(xhash_lthis), XHASH_TABLE(xhash_rthis))

#define XHASH_ECTXT_UPDATE(xhash_this, xlst_ctxt)     \
            XLST_ECTXT_UPDATE(XHASH_TABLE(xhash_this), (xlst_ctxt))

#define XHASH_MAX_SIZE(xhash_this)  XLST_MAX_SIZE(XHASH_TABLE(xhash_this))

//====================================================================

#define XHASH_ELEM_EQ(xhash_this, xhash_eml, xhash_emr) \
    ((xhash_this)->xhash_eqfunc(xhash_eml, xhash_emr, XHASH_ECTXT(xhash_this)))

#define XHASH_TABLE_SIZE(xhash_this)  ((xhash_this)->xhash_table.xlst_csize)

#define XHASH_TABLE_FUNC(xfunc, ...)  std_list_##xfunc(##__VA_ARGS__)

#define XHASH_TABLE_CALL(xfunc, xhash_this, ...) \
    std_list_##xfunc(&(xhash_this)->xhash_table, ##__VA_ARGS__)

#define XHASH_LTER_BEGIN(xhash_this)  ((xhash_lter_t)XLST_ITER_BEGIN(XHASH_TABLE(xhash_this)))
#define XHASH_LTER_END(xhash_this)    ((xhash_lter_t)XLST_ITER_END(XHASH_TABLE(xhash_this)))
#define XHASH_LTER_RBEGIN(xhash_this) ((xhash_lter_t)XLST_ITER_RBEGIN(XHASH_TABLE(xhash_this)))
#define XHASH_LTER_REND(xhash_this)   ((xhash_lter_t)XLST_ITER_REND(XHASH_TABLE(xhash_this)))

#define XHASH_LTER_ELEM(xhash_lter)   ((xhash_elem_t)XLST_ITER_ELEM(xhash_lter))
#define XHASH_LTER_NEXT(xhash_lter)   ((xhash_lter_t)((xhash_lter)->xiter_next))
#define XHASH_LTER_PREV(xhash_lter)   ((xhash_lter_t)((xhash_lter)->xiter_prev))

#if XLST_CHECKED_OWNER
#define XHASH_LTER_REOWNER(xhash_this, xhash_lter) \
    ((xhash_lter)->xlst_owner = XHASH_TABLE(xhash_this))
#else // !XLST_CHECKED_OWNER
#define XHASH_LTER_REOWNER(xhash_this, xhash_lter)
#endif // XLST_CHECKED_OWNER

#define XHASH_LTER_INSERT(xhash_this, xhash_iter, xhash_lter) \
    do                                                        \
    {                                                         \
        XLST_ITER_INSERT((xhash_iter), (xhash_lter));         \
        XHASH_LTER_REOWNER((xhash_this), (xhash_lter));       \
        ++(xhash_this)->xhash_table.xlst_csize;               \
    } while (0)

#define XHASH_LTER_REMOVE(xhash_this, xhash_lter) \
    do                                            \
    {                                             \
        XLST_ITER_RMNODE(xhash_lter);             \
        --(xhash_this)->xhash_table.xlst_csize;   \
    } while (0)

#define XHASH_LTER_SPLICE(xlter_pos, xlter_first, xlter_last, xlter_swap) \
    XLST_ITER_SPLICE(xlter_pos, xlter_first, xlter_last, xlter_swap)

#define XHASH_BUCKET_VPTR(xhash_this) ((xhash_this)->xhash_bucket.xhash_vptr)
#define XHASH_BUCKET_SIZE(xhash_this) ((xhash_this)->xhash_bucket.xhash_vlen)
#define XHASH_BUCKET_MASK(xhash_this) ((xhash_this)->xhash_bucket.xhash_mask)
#define XHASH_BUCKET_MAXF(xhash_this) ((xhash_this)->xhash_bucket.xhash_maxf)

#define XHASH_BUCKET_RESET(xhash_this)                      \
    do                                                      \
    {                                                       \
        (xhash_this)->xhash_bucket.xhash_vptr = XHASH_NULL; \
        (xhash_this)->xhash_bucket.xhash_vlen = 0;          \
        (xhash_this)->xhash_bucket.xhash_mask = 0;          \
        (xhash_this)->xhash_bucket.xhash_maxf = 1.0F;       \
    } while (0)

#define XHASH_BUCKET_NKEY(xhash_this, xhash_elem) \
    (xhash_this)->xhash_nkfunc((xhash_elem), XHASH_ECTXT(xhash_this))

#define XHASH_BUCKET_VKEY(xhash_this, xhash_nkey) \
    (&(xhash_this)->xhash_bucket.xhash_vptr[      \
        (xhash_nkey) & (xhash_this)->xhash_bucket.xhash_mask])

#define XHASH_BUCKET_VTER(xhash_this, xhash_elem) \
    XHASH_BUCKET_VKEY((xhash_this), XHASH_BUCKET_NKEY((xhash_this), (xhash_elem)))

#define XHASH_BUCKET_MINSIZE  8

#define XHASH_BUCKET_MAX_SIZE(xhash_this)  \
    ((xhash_size_t)(((xhash_size_t)~0) / sizeof(xhash_vkey_t)))

//====================================================================

////////////////////////////////////////////////////////////////////////////////

#endif // __STD_HASH_INL__
